/**
 * Created by forcht on 2018/4/30.
 */
public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        int[][] dp=new int[m][n];
        for(int i=m-1;i>=0;i--){
            if(obstacleGrid[i][n-1]==1)break;
            dp[i][n - 1] = 1;
        }
        for(int i=n-1;i>=0;i--){
            if (obstacleGrid[m-1][i]==1)break;
            dp[m-1][i]=1;
        }
        for(int i=m-2;i>=0;i--){
            for(int j=n-2;j>=0;j--){
               if (obstacleGrid[i][j]==0){
                   if(obstacleGrid[i+1][j]==0)
                       dp[i][j]=dp[i+1][j];
                   if (obstacleGrid[i][j+1]==0)
                       dp[i][j]=dp[i][j]+dp[i][j+1];
               }
            }
        }
        return dp[0][0];
    }
}
